
////////////////////////////////////////////////////////////////////////////
//	File Name: TSparseVector.inl		Last modification at : 2/13/2003 2:01:32 AM
//	Copyright 1999-2003 Microsoft Corporation. All Rights Reserved.
//
//	Author:      Rong Xiao
//	Email :      t-rxiao@microsoft.com
//
//	Description : 
//
//	Revision History: 
//
////////////////////////////////////////////////////////////////////////////

template <typename T>
inline int TSparseVector<T>::SearchIndex( unsigned nDim) const
{
	assert ( nDim>=0 && nDim < m_Dim);
	unsigned index;
	int i=0;
	int nLen=GetLen();
	int low, high;	
	//Using binary search for index
	if ( nLen==0 )
		return -1;

	for ( low=0, high=nLen-1;  high>=low;  )          {
		i = (high+low) / 2;
		index=m_IndexList[i];
		if ( nDim == index ) return i;
		if ( nDim < index )  high = i-1;
		else             low  = i+1;
	}
	if ( nDim > index )
		return i-nLen;
	else 
		return i-nLen-1;
}


//***************************************************
//	Section 6: Data Operating
//***************************************************
	/**********************************************************
	Section 6.1: Set/Get Values
	**********************************************************/

template <typename T>
inline void TSparseVector<T>::push_back(unsigned int index, T Value)
{
	assert ( index<m_Dim && index>=0);

	m_IndexList.push_back( index );
	m_ValueList.push_back( Value );
}

// @cmember set an element's value,base 0
template <typename T>
inline void TSparseVector<T>::SetAt(int nDim, T NewValue) 
{
	int nRet=SearchIndex(nDim);
	int nLen=m_ValueList.size();
	int insertPos;
	
	if (nRet<0) {
		insertPos=nRet+nLen+1;
		if ( insertPos<nLen) {
			m_IndexList.insert(m_IndexList.begin()+insertPos, nDim);
			m_ValueList.insert(m_ValueList.begin()+insertPos, NewValue);
		}
		else {
			m_IndexList.push_back(nDim);
			m_ValueList.push_back(NewValue);
		}
	}
	else
		m_ValueList[nRet] = NewValue;
}

	// @cmember get an element's value,base 0
template <typename T>
inline T TSparseVector<T>::GetAt(int nDim) const
{
	int nRet=SearchIndex(nDim);
	if (nRet<0)
		return 0;
	else
		return  m_ValueList[nRet];
}

 	
	// @cmember write down the vector
template <typename T>
inline int TSparseVector<T>::Write(const char* szFname, bool bBinary) const
{
	assert(szFname);
	std::ofstream Fout;
	
	if ( bBinary==true ) Fout.open(szFname, std::ios::binary);
	else Fout.open(szFname);
	
    return Write(Fout,bBinary);
}

template <typename T>
inline int TSparseVector<T>::Write(std::ostream& Fout, bool bBinary) const
{
    assert(Fout);
    if (!Fout) return -1;
	
	int nLen=m_IndexList.size();
		
	if ( bBinary==true ) {
		Fout.write((const char*)&m_Dim, sizeof(int));
		Fout.write((const char*)&nLen, sizeof(int));
		if ( nLen>0 ) {
			Fout.write(GetSparseIndexPtr(),nLen*sizeof(int));
			Fout.write(GetSparseValuePtr(),nLen*sizeof(T));
		}
	}
	else {
		Fout << m_Dim  << std::endl;	
		Fout << nLen << ' ';
		for ( int i=0; i<nLen; i++) {
			Fout << m_IndexList[i] << ':';
			IOTraits<T>::Write(Fout, m_ValueList[i]);
			Fout << ' ';
		}
	}
	return 0;
}
    // @cmember read the vector
template <typename T>
inline int TSparseVector<T>::Read(const char* szFname, bool bBinary)
{
	assert(szFname);
	std::ifstream Fin;
	if (bBinary==true)
		Fin.open(szFname,std::ios::binary);
	else
		Fin.open(szFname);
	
    return Read(Fin, bBinary);  
}

template <typename T>
inline int TSparseVector<T>::Read(std::istream& Fin, bool bBinary)
{
	assert(Fin);
    if (!Fin) return -1;
	
	int nLen;

	if ( true==bBinary ) {
		Fin.read((char*)&m_Dim,sizeof(int));
		Fin.read((char*)&nLen,sizeof(int));
		if ( nLen>0 ) {
			ResizeSparseBuffer(nLen);
			Fin.read(GetSparseIndexPtr(),nLen*sizeof(int));
			Fin.read(GetSparseValuePtr(),nLen*sizeof(T));
		}
	}
	else {
		T Value;
		char cSep;
		int index;

		Fin >> m_Dim >> nLen;
		if ( nLen>0 ) {
			ReserveSparseBuffer(nLen);

			for ( int i=0; i<nLen; i++ ) {
				Fin >> index >>cSep ;
				IOTraits<T>::Read(Fin, Value);
				push_back(index,Value);
			}
		}
	}

	return 0;
}

	/*********************************************************
		Section 6.3: Type Cast operation
	*********************************************************/
	// @cmember Type convertor between difference types

template <typename T> 
inline TSparseVector<T>::operator TCharSparseVector() const
{
	TCharSparseVector retVal(m_Dim);
	for ( int i=0; i<GetLen(); i++) {
		retVal.push_back(m_IndexList[i], (char) m_ValueList[i]);
	}
	return retVal;
}

template <typename T> 
inline TSparseVector<T>::operator TShortSparseVector() const
{
	TShortSparseVector retVal(m_Dim);
	for ( int i=0; i<GetLen(); i++) {
		retVal.push_back(m_IndexList[i], (short) m_ValueList[i]);
	}
	return retVal;
}

template <typename T> 
inline TSparseVector<T>::operator TIntSparseVector() const
{
	TIntSparseVector retVal(m_Dim);
	for ( int i=0; i<GetLen(); i++) {
		retVal.push_back(m_IndexList[i], (int) m_ValueList[i]);
	}
	return retVal;

}

template <typename T> 
inline TSparseVector<T>::operator TByteSparseVector() const
{
	TByteSparseVector retVal(m_Dim);
	for ( int i=0; i<GetLen(); i++) {
		retVal.push_back(m_IndexList[i], (BYTE) m_ValueList[i]);
	}
	return retVal;
	
}

template <typename T> 
inline TSparseVector<T>::operator TUShortSparseVector() const
{
	TUShortSparseVector retVal(m_Dim);
	for ( int i=0; i<GetLen(); i++) {
		retVal.push_back(m_IndexList[i], (unsigned short) m_ValueList[i]);
	}
	return retVal;
	
}

template <typename T> 
inline TSparseVector<T>::operator TUIntSparseVector() const
{
	TUIntSparseVector retVal(m_Dim);
	for ( int i=0; i<GetLen(); i++) {
		retVal.push_back(m_IndexList[i], (unsigned int) m_ValueList[i]);
	}
	return retVal;

}

template <typename T> 
inline TSparseVector<T>::operator TFloatSparseVector() const
{
	TFloatSparseVector retVal(m_Dim);
	for ( int i=0; i<GetLen(); i++) {
		retVal.push_back(m_IndexList[i], (float) m_ValueList[i]);
	}
	return retVal;
	
}

template <typename T> 
inline TSparseVector<T>::operator TDoubleSparseVector() const
{
	TDoubleSparseVector retVal(m_Dim);
	for ( int i=0; i<GetLen(); i++) {
		retVal.push_back(m_IndexList[i], (double) m_ValueList[i]);
	}
	return retVal;
	
}

template <typename T> 
inline TSparseVector<T>::operator TSparseMatrix<T>() const
{
	TSparseMatrix<T> retVal( 1, m_Dim);
	retVal[0]=*this;
	return retVal;
}

template <typename T> 
inline TSparseVector<T>::operator TMatrix<T>() const
{
	TMatrix<T> retVal(1,m_Dim);
	for ( int i=0;i<GetLen(); i++ )
		retVal(0,GetSparseIndex(i))=GetSparseValue(i);
	return retVal;
}

template <typename T> 
inline TSparseVector<T>::operator TVector<T>() const
{
	TVector<T> retVal(m_Dim);
	for ( int i=0; i<GetLen(); i++)
		retVal[m_IndexList[i]]=m_ValueList[i];
	return retVal;
}


//***************************************************
//	Section 7:  OverRide Operation 
//***************************************************
	// @cmember Operator [], used to access the element of Vector
	//		This is const version, It is necessary.
template <typename T> 
inline T TSparseVector<T>::operator [](int nDim) const 
{
	return GetAt(nDim);
}
	

// @cmember Vector multiple
template <typename T> 
inline T TSparseVector<T>::operator*(const TSparseVector<T>& ref) const
{
	T Sum=0;

	for ( i=0, j=0; i<GetLen(), j<ref.GetLen();) {
		if ( m_IndexList[i] < ref.m_IndexList[j] )
			i++;
		else if ( m_IndexList[i] > ref.m_IndexList[j] )
			j++;
		else		
			Sum+=m_ValueList[i] * ref.m_ValueList[j];
	}
	return Sum;
}

	// @cmember Vector multiple
template <typename T> 
inline T TSparseVector<T>::operator*(const TVector<T>& ref) const
{
	T Sum=0;
	
	for ( int i=0; i<GetLen(); i++) 
		Sum+=m_ValueList[i] * ref[m_IndexList[i]];

	return Sum;	
}	

	// @cmember Vector multiple
template <typename T> 
inline TVector<T> TSparseVector<T>::operator*(const TSparseMatrix<T>& ref) const
{
	TVector<T> retVal(ref.GetCols());
	TSparseMatrix<T> tmp;
	tmp=ref.Transpose();
	for ( int i=0; i<ref.GetCols(); i++ ) 
		retVal[i]= (*this) * tmp[i];
	return retVal;
}

	
// @cmember Vector multiple
template <typename T> 
inline TVector<T> TSparseVector<T>::operator*(const TMatrix<T>& ref) const
{
	assert ( m_Dim==ref.GetRows() );

	int nCol=ref.GetCols();
	int nLen=GetLen();
	TVector<T> retVal(nCol);
	
	for ( int j=0; j<nLen; j++) {
		for ( int i=0; i<nCol; i++ ) 
			retVal[i] += m_ValueList[j]*ref(m_IndexList[j],i) 
	}
	return retVal;
}

	
	// @cmember multiple a numeric
template <typename T> 
inline TSparseVector<T> TSparseVector<T>::operator*(const T scale) const
{
	TSparseVector<T> retVal(*this);
	for ( int i=0; i<GetLen(); i++ )
		retVal.m_ValueList[i]= m_ValueList[i]*scale;
	return retVal;
}

	// @cmember all the elements divide a numeric
template <typename T> 
inline TSparseVector<T> TSparseVector<T>::operator/(const T scale) const
{
	TSparseVector<T> retVal(*this);
	for ( int i=0; i<GetLen(); i++ )
		retVal.m_ValueList[i]= m_ValueList[i]/scale;
	return retVal;
}
	
	// @cmember multiple a numeric to all the element
template <typename T> 
void TSparseVector<T>::operator*=(const T scale)
{
	for ( int i=0; i<GetLen(); i++ )
		m_ValueList[i]*=scale;
}

	// @cmember each elements divide a numeric
template <typename T> 
void TSparseVector<T>::operator/=(const T scale)
{
	for ( int i=0; i<GetLen(); i++ )
		m_ValueList[i]/=scale;
}


//************************************************
//	Section 8:	Vector Computation 
//************************************************
//return the max value of vect
template <typename T> 
inline T TSparseVector<T>::Max(void) const
{
	T max=0;

	assert ( m_Dim>0 );	
	if ( GetLen() == m_Dim ) 
		max = m_ValueList[0];

	for ( unsigned int i=0; i<GetLen(); i++) {
		if ( m_ValueList[i]>max )	
			max = m_ValueList[i];
	}
	return max;
}

//return the min value of vect
template <typename T> 
inline T TSparseVector<T>::Min(void) const
{
	T min=0;
	
	assert ( m_Dim>0 );	
	if ( GetLen() == m_Dim ) 
		min = m_ValueList[0];

	for ( unsigned int i=0; i<GetLen(); i++) {
		if ( m_ValueList[i]<min )	
			min = m_ValueList[i];
	}
	return min;
}

//return the max value pos of vect
template <typename T> 
inline int TSparseVector<T>::MaxPos(void) const
{
	T max;
	unsigned int i, maxPos;

	assert ( m_Dim>0 );	

	if ( GetLen()>0 ) {
		max=m_ValueList[0];
		maxPos=m_IndexList[0];
	}
	else 
		return 0;
		
	for ( i=1; i<GetLen(); i++) {
		if ( m_ValueList[i]>max )	{
			max = m_ValueList[i];
			maxPos=m_IndexList[i];
		}
	}
	if ( max>=0 || GetLen()==m_Dim)
		return maxPos;
	else { //Search for the first zero position
		for (i=0; i<GetLen(); i++ ) {
			if ( i<m_IndexList[i])
				return i;
		}
		return i;
	}
}

//return the min value pos of vect
template <typename T> 
inline int TSparseVector<T>::MinPos(void) const
{
	T min;
	unsigned int i, minPos;
	
	assert ( m_Dim>0 );	
	
	if ( GetLen()>0 ) {
		min=m_ValueList[0];
		minPos=m_IndexList[0];
	}
	else 
		return 0;
	
	for ( i=1; i<GetLen(); i++) {
		if ( m_ValueList[i]<min )	{
			min = m_ValueList[i];
			minPos=m_IndexList[i];
		}
	}
	if ( min <=0 || GetLen()==m_Dim)
		return minPos;
	else { //Search for the first zero position
		for (i=0; i<GetLen(); i++ ) {
			if ( i<m_IndexList[i])
				return i;
		}
		return i;
	}
}


	// @cmember return sum of all elements
template <typename T> 
inline double TSparseVector<T>::Sum(void) const
{
	double Sum=0;
	for ( int i=0; i<GetLen(); i++ )
		Sum+=m_ValueList[i];
	return Sum;
}

template <typename T> 
inline T TSparseVector<T>::TSum(void) const
{
	T Sum=0;
	for ( int i=0; i<GetLen(); i++ )
		Sum+=m_ValueList[i];
	
	return Sum;
}

	// @cmember return mean of Vector
template <typename T> 
inline double TSparseVector<T>::Mean(void) const
{
	return Sum()/m_Dim;
}

template <typename T> 
inline T TSparseVector<T>::TMean(void) const
{
	return TSum()/m_Dim;
}

	// Compute ABS vector
template <typename T> 
inline TSparseVector<T> TSparseVector<T>::abs(void) const
{
	TSparseVector<T> retVal(*this);

	for ( int i=0; i<GetLen(); i++ )
		retVal.m_ValueList[i] = TAbs(m_ValueList[i]);
}
	

   	// @cmember Get the Variance of this vector (in double)
template <typename T> 
inline double TSparseVector<T>::GetVariance(void) const
{
	return sqrt( GetNorm2()/m_Dim - TSquare(Mean()) );
}

    // @cmember return 2-norm the vector 
template <typename T> 
inline double TSparseVector<T>::GetNorm2(void) const
{
	double Sum=0;
	for ( int i=0; i<GetLen(); i++ )
		Sum+=TSquare(m_ValueList[i]);

	return Sum;	
}

template <typename T> 
inline T TSparseVector<T>::TGetNorm2(void) const
{
	T Sum=0;
	for ( int i=0; i<GetLen(); i++ )
		Sum+=TSquare(m_ValueList[i]);
	
	return Sum;	
}
    // @cmember return norm of the vector 
template <typename T> 
inline double TSparseVector<T>::GetNorm(void) const
{
	return sqrt(GetNorm2());
}


template <typename T> 
inline std::istream & operator >> (std::istream& is, TSparseVector<T>& vect)
{
	vect.Read(is,false);
	return is;
}

template <typename T> 
inline std::ostream & operator << (std::ostream& os, const TSparseVector<T>& vect)
{
	vect.Write(os,false);
	return os;
}
